/*
 * contrib/ltree/_ltree_gist.c
 *
 *
 * ltree[] 的 GiST 支持
 * Teodor Sigaev <teodor@stack.net>
 */
#include "postgres.h"

#include "access/gist.h"
#include "access/reloptions.h"
#include "access/stratnum.h"
#include "crc32.h"
#include "ltree.h"
#include "port/pg_bitutils.h"

PG_FUNCTION_INFO_V1(_ltree_compress);
PG_FUNCTION_INFO_V1(_ltree_same);
PG_FUNCTION_INFO_V1(_ltree_union);
PG_FUNCTION_INFO_V1(_ltree_penalty);
PG_FUNCTION_INFO_V1(_ltree_picksplit);
PG_FUNCTION_INFO_V1(_ltree_consistent);
PG_FUNCTION_INFO_V1(_ltree_gist_options);

#define GETENTRY(vec,pos) ((ltree_gist *) DatumGetPointer((vec)->vector[(pos)].key))
#define NEXTVAL(x) ( (ltree*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) )

#define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )


static void fc_hashing(BITVECP fc_sign, ltree *fc_t, int fc_siglen)
{
	int			fc_tlen = fc_t->numlevel;
	ltree_level *fc_cur = LTREE_FIRST(fc_t);
	int			fc_hash;

	while (fc_tlen > 0)
	{
		fc_hash = ltree_crc32_sz(fc_cur->name, fc_cur->len);
		AHASH(fc_sign, fc_hash, fc_siglen);
		fc_cur = LEVEL_NEXT(fc_cur);
		fc_tlen--;
	}
}

Datum _ltree_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	GISTENTRY  *fc_retval = fc_entry;
	int			fc_siglen = LTREE_GET_ASIGLEN();

	if (fc_entry->leafkey)
	{							/* ltree */
		ltree_gist *fc_key;
		ArrayType  *fc_val = DatumGetArrayTypeP(fc_entry->key);
		int			fc_num = ArrayGetNItems(ARR_NDIM(fc_val), ARR_DIMS(fc_val));
		ltree	   *fc_item = (ltree *) ARR_DATA_PTR(fc_val);

		if (ARR_NDIM(fc_val) > 1)
			ereport(ERROR,
					(errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
					 errmsg("array must be one-dimensional")));
		if (array_contains_nulls(fc_val))
			ereport(ERROR,
					(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
					 errmsg("array must not contain nulls")));

		fc_key = ltree_gist_alloc(false, NULL, fc_siglen, NULL, NULL);

		while (fc_num > 0)
		{
			fc_hashing(LTG_SIGN(fc_key), fc_item, fc_siglen);
			fc_num--;
			fc_item = NEXTVAL(fc_item);
		}

		fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_key),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset, false);
	}
	else if (!LTG_ISALLTRUE(fc_entry->key))
	{
		int32		i;
		ltree_gist *fc_key;
		BITVECP		fc_sign = LTG_SIGN(DatumGetPointer(fc_entry->key));

		ALOOPBYTE(fc_siglen)
		{
			if ((fc_sign[i] & 0xff) != 0xff)
				PG_RETURN_POINTER(fc_retval);
		}

		fc_key = ltree_gist_alloc(true, fc_sign, fc_siglen, NULL, NULL);
		fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_key),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset, false);
	}
	PG_RETURN_POINTER(fc_retval);
}

Datum _ltree_same(PG_FUNCTION_ARGS)
{
	ltree_gist *fc_a = (ltree_gist *) PG_GETARG_POINTER(0);
	ltree_gist *fc_b = (ltree_gist *) PG_GETARG_POINTER(1);
	bool	   *fc_result = (bool *) PG_GETARG_POINTER(2);
	int			fc_siglen = LTREE_GET_ASIGLEN();

	if (LTG_ISALLTRUE(fc_a) && LTG_ISALLTRUE(fc_b))
		*fc_result = true;
	else if (LTG_ISALLTRUE(fc_a))
		*fc_result = false;
	else if (LTG_ISALLTRUE(fc_b))
		*fc_result = false;
	else
	{
		int32		i;
		BITVECP		fc_sa = LTG_SIGN(fc_a),
					fc_sb = LTG_SIGN(fc_b);

		*fc_result = true;
		ALOOPBYTE(fc_siglen)
		{
			if (fc_sa[i] != fc_sb[i])
			{
				*fc_result = false;
				break;
			}
		}
	}
	PG_RETURN_POINTER(fc_result);
}

static int32 fc_unionkey(BITVECP fc_sbase, ltree_gist *fc_add, int fc_siglen)
{
	int32		i;
	BITVECP		fc_sadd = LTG_SIGN(fc_add);

	if (LTG_ISALLTRUE(fc_add))
		return 1;

	ALOOPBYTE(fc_siglen)
		fc_sbase[i] |= fc_sadd[i];
	return 0;
}

Datum _ltree_union(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	int		   *fc_size = (int *) PG_GETARG_POINTER(1);
	int			fc_siglen = LTREE_GET_ASIGLEN();
	int32		fc_i;
	ltree_gist *fc_result = ltree_gist_alloc(false, NULL, fc_siglen, NULL, NULL);
	BITVECP		fc_base = LTG_SIGN(fc_result);

	for (fc_i = 0; fc_i < fc_entryvec->n; fc_i++)
	{
		if (fc_unionkey(fc_base, GETENTRY(fc_entryvec, fc_i), fc_siglen))
		{
			fc_result->flag |= LTG_ALLTRUE;
			SET_VARSIZE(fc_result, LTG_HDRSIZE);
			break;
		}
	}

	*fc_size = VARSIZE(fc_result);

	PG_RETURN_POINTER(fc_result);
}

static int32 fc_sizebitvec(BITVECP fc_sign, int fc_siglen)
{
	return pg_popcount((const char *) fc_sign, fc_siglen);
}

static int fc_hemdistsign(BITVECP fc_a, BITVECP fc_b, int fc_siglen)
{
	int			i,
				fc_diff,
				fc_dist = 0;

	ALOOPBYTE(fc_siglen)
	{
		fc_diff = (unsigned char) (fc_a[i] ^ fc_b[i]);
		/* 在这里使用 popcount 函数不太可能获胜 */
		fc_dist += pg_number_of_ones[fc_diff];
	}
	return fc_dist;
}

static int fc_hemdist(ltree_gist *fc_a, ltree_gist *fc_b, int fc_siglen)
{
	if (LTG_ISALLTRUE(fc_a))
	{
		if (LTG_ISALLTRUE(fc_b))
			return 0;
		else
			return ASIGLENBIT(fc_siglen) - fc_sizebitvec(LTG_SIGN(fc_b), fc_siglen);
	}
	else if (LTG_ISALLTRUE(fc_b))
		return ASIGLENBIT(fc_siglen) - fc_sizebitvec(LTG_SIGN(fc_a), fc_siglen);

	return fc_hemdistsign(LTG_SIGN(fc_a), LTG_SIGN(fc_b), fc_siglen);
}


Datum _ltree_penalty(PG_FUNCTION_ARGS)
{
	ltree_gist *fc_origval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(0))->key);
	ltree_gist *fc_newval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(1))->key);
	float	   *fc_penalty = (float *) PG_GETARG_POINTER(2);
	int			fc_siglen = LTREE_GET_ASIGLEN();

	*fc_penalty = fc_hemdist(fc_origval, fc_newval, fc_siglen);
	PG_RETURN_POINTER(fc_penalty);
}

typedef struct
{
	OffsetNumber pos;
	int32		cost;
} SPLITCOST;

static int fc_comparecost(const void *fc_a, const void *fc_b)
{
	return ((const SPLITCOST *) fc_a)->cost - ((const SPLITCOST *) fc_b)->cost;
}

Datum _ltree_picksplit(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	GIST_SPLITVEC *fc_v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
	int			fc_siglen = LTREE_GET_ASIGLEN();
	OffsetNumber fc_k,
				fc_j;
	ltree_gist *fc_datum_l,
			   *fc_datum_r;
	BITVECP		fc_union_l,
				fc_union_r;
	int32		fc_size_alpha,
				fc_size_beta;
	int32		fc_size_waste,
				fc_waste = -1;
	int32		fc_nbytes;
	OffsetNumber fc_seed_1 = 0,
				fc_seed_2 = 0;
	OffsetNumber *fc_left,
			   *fc_right;
	OffsetNumber fc_maxoff;
	BITVECP		fc_ptr;
	int			i;
	SPLITCOST  *fc_costvector;
	ltree_gist *fc__k,
			   *fc__j;

	fc_maxoff = fc_entryvec->n - 2;
	fc_nbytes = (fc_maxoff + 2) * sizeof(OffsetNumber);
	fc_v->spl_left = (OffsetNumber *) palloc(fc_nbytes);
	fc_v->spl_right = (OffsetNumber *) palloc(fc_nbytes);

	for (fc_k = FirstOffsetNumber; fc_k < fc_maxoff; fc_k = OffsetNumberNext(fc_k))
	{
		fc__k = GETENTRY(fc_entryvec, fc_k);
		for (fc_j = OffsetNumberNext(fc_k); fc_j <= fc_maxoff; fc_j = OffsetNumberNext(fc_j))
		{
			fc_size_waste = fc_hemdist(fc__k, GETENTRY(fc_entryvec, fc_j), fc_siglen);
			if (fc_size_waste > fc_waste)
			{
				fc_waste = fc_size_waste;
				fc_seed_1 = fc_k;
				fc_seed_2 = fc_j;
			}
		}
	}

	fc_left = fc_v->spl_left;
	fc_v->spl_nleft = 0;
	fc_right = fc_v->spl_right;
	fc_v->spl_nright = 0;

	if (fc_seed_1 == 0 || fc_seed_2 == 0)
	{
		fc_seed_1 = 1;
		fc_seed_2 = 2;
	}

	/* 形成初始 .. */
	fc_datum_l = ltree_gist_alloc(LTG_ISALLTRUE(GETENTRY(fc_entryvec, fc_seed_1)),
							   LTG_SIGN(GETENTRY(fc_entryvec, fc_seed_1)),
							   fc_siglen, NULL, NULL);

	fc_datum_r = ltree_gist_alloc(LTG_ISALLTRUE(GETENTRY(fc_entryvec, fc_seed_2)),
							   LTG_SIGN(GETENTRY(fc_entryvec, fc_seed_2)),
							   fc_siglen, NULL, NULL);

	fc_maxoff = OffsetNumberNext(fc_maxoff);
	/* 在 ... 之前排序 */
	fc_costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * fc_maxoff);
	for (fc_j = FirstOffsetNumber; fc_j <= fc_maxoff; fc_j = OffsetNumberNext(fc_j))
	{
		fc_costvector[fc_j - 1].pos = fc_j;
		fc__j = GETENTRY(fc_entryvec, fc_j);
		fc_size_alpha = fc_hemdist(fc_datum_l, fc__j, fc_siglen);
		fc_size_beta = fc_hemdist(fc_datum_r, fc__j, fc_siglen);
		fc_costvector[fc_j - 1].cost = Abs(fc_size_alpha - fc_size_beta);
	}
	qsort((void *) fc_costvector, fc_maxoff, sizeof(SPLITCOST), fc_comparecost);

	fc_union_l = LTG_SIGN(fc_datum_l);
	fc_union_r = LTG_SIGN(fc_datum_r);

	for (fc_k = 0; fc_k < fc_maxoff; fc_k++)
	{
		fc_j = fc_costvector[fc_k].pos;
		if (fc_j == fc_seed_1)
		{
			*fc_left++ = fc_j;
			fc_v->spl_nleft++;
			continue;
		}
		else if (fc_j == fc_seed_2)
		{
			*fc_right++ = fc_j;
			fc_v->spl_nright++;
			continue;
		}
		fc__j = GETENTRY(fc_entryvec, fc_j);
		fc_size_alpha = fc_hemdist(fc_datum_l, fc__j, fc_siglen);
		fc_size_beta = fc_hemdist(fc_datum_r, fc__j, fc_siglen);

		if (fc_size_alpha < fc_size_beta + WISH_F(fc_v->spl_nleft, fc_v->spl_nright, 0.00001))
		{
			if (LTG_ISALLTRUE(fc_datum_l) || LTG_ISALLTRUE(fc__j))
			{
				if (!LTG_ISALLTRUE(fc_datum_l))
					MemSet((void *) fc_union_l, 0xff, fc_siglen);
			}
			else
			{
				fc_ptr = LTG_SIGN(fc__j);
				ALOOPBYTE(fc_siglen)
					fc_union_l[i] |= fc_ptr[i];
			}
			*fc_left++ = fc_j;
			fc_v->spl_nleft++;
		}
		else
		{
			if (LTG_ISALLTRUE(fc_datum_r) || LTG_ISALLTRUE(fc__j))
			{
				if (!LTG_ISALLTRUE(fc_datum_r))
					MemSet((void *) fc_union_r, 0xff, fc_siglen);
			}
			else
			{
				fc_ptr = LTG_SIGN(fc__j);
				ALOOPBYTE(fc_siglen)
					fc_union_r[i] |= fc_ptr[i];
			}
			*fc_right++ = fc_j;
			fc_v->spl_nright++;
		}
	}

	*fc_right = *fc_left = FirstOffsetNumber;

	fc_v->spl_ldatum = PointerGetDatum(fc_datum_l);
	fc_v->spl_rdatum = PointerGetDatum(fc_datum_r);

	PG_RETURN_POINTER(fc_v);
}

static bool fc_gist_te(ltree_gist *fc_key, ltree *fc_query, int fc_siglen)
{
	ltree_level *fc_curq = LTREE_FIRST(fc_query);
	BITVECP		fc_sign = LTG_SIGN(fc_key);
	int			fc_qlen = fc_query->numlevel;
	unsigned int fc_hv;

	if (LTG_ISALLTRUE(fc_key))
		return true;

	while (fc_qlen > 0)
	{
		fc_hv = ltree_crc32_sz(fc_curq->name, fc_curq->len);
		if (!GETBIT(fc_sign, AHASHVAL(fc_hv, fc_siglen)))
			return false;
		fc_curq = LEVEL_NEXT(fc_curq);
		fc_qlen--;
	}

	return true;
}

typedef struct LtreeSignature
{
	BITVECP		sign;
	int			siglen;
} LtreeSignature;

static bool fc_checkcondition_bit(void *fc_cxt, ITEM *fc_val)
{
	LtreeSignature *fc_sig = fc_cxt;

	return (FLG_CANLOOKSIGN(fc_val->flag)) ? GETBIT(fc_sig->sign, AHASHVAL(fc_val->val, fc_sig->siglen)) : true;
}

static bool fc_gist_qtxt(ltree_gist *fc_key, ltxtquery *fc_query, int fc_siglen)
{
	LtreeSignature fc_sig;

	if (LTG_ISALLTRUE(fc_key))
		return true;

	fc_sig.sign = LTG_SIGN(fc_key);
	fc_sig.siglen = fc_siglen;

	return ltree_execute(GETQUERY(fc_query),
						 &fc_sig, false,
						 fc_checkcondition_bit);
}

static bool fc_gist_qe(ltree_gist *fc_key, lquery *fc_query, int fc_siglen)
{
	lquery_level *fc_curq = LQUERY_FIRST(fc_query);
	BITVECP		fc_sign = LTG_SIGN(fc_key);
	int			fc_qlen = fc_query->numlevel;

	if (LTG_ISALLTRUE(fc_key))
		return true;

	while (fc_qlen > 0)
	{
		if (fc_curq->numvar && LQL_CANLOOKSIGN(fc_curq))
		{
			bool		fc_isexist = false;
			int			fc_vlen = fc_curq->numvar;
			lquery_variant *fc_curv = LQL_FIRST(fc_curq);

			while (fc_vlen > 0)
			{
				if (GETBIT(fc_sign, AHASHVAL(fc_curv->val, fc_siglen)))
				{
					fc_isexist = true;
					break;
				}
				fc_curv = LVAR_NEXT(fc_curv);
				fc_vlen--;
			}
			if (!fc_isexist)
				return false;
		}

		fc_curq = LQL_NEXT(fc_curq);
		fc_qlen--;
	}

	return true;
}

static bool fc__arrq_cons(ltree_gist *fc_key, ArrayType *fc__query, int fc_siglen)
{
	lquery	   *fc_query = (lquery *) ARR_DATA_PTR(fc__query);
	int			fc_num = ArrayGetNItems(ARR_NDIM(fc__query), ARR_DIMS(fc__query));

	if (ARR_NDIM(fc__query) > 1)
		ereport(ERROR,
				(errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
				 errmsg("array must be one-dimensional")));
	if (array_contains_nulls(fc__query))
		ereport(ERROR,
				(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
				 errmsg("array must not contain nulls")));

	while (fc_num > 0)
	{
		if (fc_gist_qe(fc_key, fc_query, fc_siglen))
			return true;
		fc_num--;
		fc_query = (lquery *) NEXTVAL(fc_query);
	}
	return false;
}

Datum _ltree_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	void	   *fc_query = (void *) PG_DETOAST_DATUM(PG_GETARG_DATUM(1));
	StrategyNumber fc_strategy = (StrategyNumber) PG_GETARG_UINT16(2);

	/* Oid		subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	int			fc_siglen = LTREE_GET_ASIGLEN();
	ltree_gist *fc_key = (ltree_gist *) DatumGetPointer(fc_entry->key);
	bool		fc_res = false;

	/* 此函数处理的所有情况都是不准确的 */
	*fc_recheck = true;

	switch (fc_strategy)
	{
		case 10:
		case 11:
			fc_res = fc_gist_te(fc_key, (ltree *) fc_query, fc_siglen);
			break;
		case 12:
		case 13:
			fc_res = fc_gist_qe(fc_key, (lquery *) fc_query, fc_siglen);
			break;
		case 14:
		case 15:
			fc_res = fc_gist_qtxt(fc_key, (ltxtquery *) fc_query, fc_siglen);
			break;
		case 16:
		case 17:
			fc_res = fc__arrq_cons(fc_key, (ArrayType *) fc_query, fc_siglen);
			break;
		default:
			/* 内部错误 */
			elog(ERROR, "unrecognized StrategyNumber: %d", fc_strategy);
	}
	PG_FREE_IF_COPY(fc_query, 1);
	PG_RETURN_BOOL(fc_res);
}

Datum _ltree_gist_options(PG_FUNCTION_ARGS)
{
	local_relopts *fc_relopts = (local_relopts *) PG_GETARG_POINTER(0);

	init_local_reloptions(fc_relopts, sizeof(LtreeGistOptions));
	add_local_int_reloption(fc_relopts, "siglen", "signature length",
							LTREE_ASIGLEN_DEFAULT, 1, LTREE_ASIGLEN_MAX,
							offsetof(LtreeGistOptions, siglen));

	PG_RETURN_VOID();
}
